#include "linearList.h"
using namespace std;

sequenceList::sequenceList(const int& maxCapcity, const int& curNumberOfItem, float myList[])
{
	this->maxCapcity = maxCapcity;
	this->curNumberOfItem = curNumberOfItem;
	this->myList = new float[maxCapcity];
	for (int i = 0; i < curNumberOfItem; i++) {
		this->myList[i] = myList[i];
	}
}


sequenceList::~sequenceList() {
	delete[]myList;
}

//顺序表打印
void sequenceList::print()
{
	cout << curNumberOfItem << ":";

	for (int i = 0; i < curNumberOfItem - 1; i++)
	{
		cout << myList[i] << ",";
	}

	cout << myList[curNumberOfItem - 1] << endl;
}

//顺序表添加元素
bool sequenceList::addItem(const float& val) {
	if (this->curNumberOfItem == this->maxCapcity)return false;
	this->myList[curNumberOfItem] = val;
	this->curNumberOfItem++;
	return true;
}

//顺序表插入元素 
bool sequenceList::insertItem(const int& index, const float& val) {//插入元素到index位置，成功返回true，失败返回false

	if (index<0 || index>this->curNumberOfItem || this->curNumberOfItem == this->maxCapcity)
		return false;

	for (int i = this->curNumberOfItem; i > index; i--) {
		this->myList[i] = this->myList[i - 1];
	}

	this->myList[index] = val;
	this->curNumberOfItem++;
	return true;
}

//顺序表删除元素
int sequenceList::deleteItem(const float& val) {//返回删除位置，找不到返回-1
	int index = -1;
	for (int i = 0; i < this->curNumberOfItem; i++) {
		if (this->myList[i] == val) {
			for (int j = i; j < this->curNumberOfItem - 1; j++) {
				this->myList[j] = this->myList[j + 1];
			}
			index = i;
			this->curNumberOfItem--;
			break;
		}
	}
	return index;
}

//顺序表查找元素（按序号找）
bool  sequenceList::locate(const int& index, float& val) {// 成功返回true，值放在val中，失败返回false
	if (index >= this->curNumberOfItem || index < 0) {
			return false;
	}
		
	val = this->myList[index];
	return true;
}

//顺序表查找元素（按值找）
int  sequenceList::locate(const float& val) {//返回找到位置，找不到返回-1
	int index = -1;
	for (int i = 0; i < this->curNumberOfItem; i++) {
		if (this->myList[i] == val) {
			index = i;
			break;
		}
	}
	return index;
}

//顺序表倒序排列元素（使用原空间）
void sequenceList::reverse() {
	int left = 0, right = this->curNumberOfItem - 1;
	while (left < right) {	
		float temp = this->myList[left];
		this->myList[left] = this->myList[right];
		this->myList[right] = temp;
		left++;
		right--;
	}
}


//初始化节点
listNode::listNode(float nodeData, listNode* succ) {
	this->data = nodeData;
	this->next = succ;
}

listNode::~listNode() {

}

//默认构造函数
linkList::linkList() {
	this->firstNode = NULL;
	this->curNode = NULL;
	this->lastNode = NULL;
	this->listSize = 0;
}

//初始化链表
linkList::linkList(const int& size, float data[]) {//初始化数组长度，初始化数组
	this->firstNode = new listNode();
	this->curNode = this->firstNode;
	this->lastNode = this->firstNode;
	this->listSize = size;
	for (int i = 0; i < this->listSize; i++) {
		listNode* newNode = new listNode(data[i], NULL);
		this->lastNode->next = newNode;
		this->lastNode = newNode;
	}
	this->curNode = this->firstNode->next;
}

//销毁链表
linkList::~linkList() {
	listNode* tempNode = this->firstNode;
	while (tempNode!= NULL) {
		listNode* nextNode = tempNode->next;
		delete tempNode;
		tempNode = nextNode;
	}
	this->listSize = 0;
}

//插入元素（头插法）
bool linkList::headInsertItem(const float& val) {//成功返回true，失败返回false
	listNode* newNode = new listNode(val, NULL);
	if (newNode == NULL)
		return false;
	newNode->next = this->firstNode->next;
	this->firstNode->next = newNode;
	//如果当前结点指向头结点，则将当前结点指向新结点。
	if (curNode == firstNode) {
		curNode = newNode;
	}
	listSize++;
	return true;
}

//插入元素（尾插法）
bool linkList::tailInsertItem(const float& val) {//成功返回true，失败返回false
	listNode* newNode = new listNode(val, NULL);
	if (newNode == NULL)
		return false;
	this->lastNode->next = newNode;
	this->lastNode = newNode;
	if (curNode == firstNode) {
		curNode = newNode;
	}
	listSize++;
	return true;
}
//插入元素
int linkList::insertItem(const int& index, const float& val) {//插入元素到index位置，成功返回插入位置，错误返回-1
	if (index<0 || index>listSize)
		return -1;
	listNode* pre_node = this->firstNode;
	for (int i = 0; i < index; i++) {
		pre_node = pre_node->next;
	}
	listNode* new_node = new listNode(val, NULL);
	new_node->next = pre_node->next;
	pre_node->next = new_node;
	//最后一个节点处插入
	if (pre_node == this->lastNode)
	{
		this->lastNode->next = new_node;
		this->lastNode = new_node;
	}
	listSize++;
	return index;
}

//删除元素
int linkList::deleteItem(const float& val) {
	int pos = -1;
	listNode* cur_node = this->firstNode->next;
	listNode* pre_node = this->firstNode;
	while (cur_node != NULL) {
		pos++;
		if (cur_node->data == val) {
			pre_node->next = cur_node->next;
			if (pos == this->listSize - 1)
			{
				this->lastNode = pre_node;
			}
			delete cur_node;
			this->listSize--;
			return pos;
		}
		pre_node = cur_node;
		cur_node = cur_node->next;
	}
	return -1;
}

//查找元素（按序号找）
bool linkList::locate(const int& index, float& val) {
	{
		return false;
	}
	listNode* cur_node = this->firstNode->next;
	for (int i = 0; i < index; i++) {
		cur_node = cur_node->next;
	}
	val = cur_node->data;
	return true;
}

//查找元素（按值找）
int linkList::locate(const float& val) {
	int index = -1;
	listNode* cur_node = this->firstNode->next;
	for (int i = 0; i < this->listSize; i++) {
		index++;
		if (cur_node->data == val) {
			return index;
		}
		cur_node = cur_node->next;
	}
	return -1;
}

//递增排序
void linkList::ascendingOrder() {
	listNode* p_node = this->firstNode->next;
	while (p_node->next != NULL) {
		listNode* q_node = p_node->next;
		while (q_node != NULL) {
			if (q_node->data < p_node->data) {
				float temp = p_node->data;
				p_node->data = q_node->data;
				q_node->data = temp;
			}
			q_node = q_node->next;
		}
		p_node = p_node->next;
	}
}

//倒序排列元素
void linkList::reverse() {
	listNode* cur_node = firstNode->next;
	listNode* pre_node = NULL;
	while (cur_node != NULL)
	{
		listNode* next_node = cur_node->next;
		cur_node->next = pre_node;
		pre_node = cur_node;
		cur_node = next_node;
	}
	lastNode = firstNode->next;
	firstNode->next = pre_node;
	curNode = pre_node;
}


//链表打印
void linkList::print()
{
	curNode = firstNode;

	cout << listSize << ":";

	while(curNode != lastNode)
	{
		if(curNode->next == lastNode)
			cout << curNode->next->data << endl;
		else
		{
			cout << curNode->next->data << ",";
		}


		curNode = curNode->next;
	}
}

int linkList::getLength() {
	return listSize;
}
void merge(linkList& A,linkList& B) {
	for (int i = 0; i < B.getLength(); i++) {
		float val;
		B.locate(i, val);
		A.headInsertItem(val);
	}
	A.ascendingOrder();
	A.reverse();
}